package Map_Set.Leetcode;

import java.util.HashMap;
import java.util.Map;

/**
 * 深拷贝链表
 */
public class Num138_copyRandomList {
    private class Node {
        int val;
        Node next;
        Node random;

        public Node(int val) {
            this.val = val;
            this.next = null;
            this.random = null;
        }
    }
    public Node copyRandomList(Node head) {
        //边界
        if(head==null){
            return null;
        }
        Map<Node,Node> nodeMap=new HashMap<>();
        //遍历原链表 构建新链表节点存储在Map中 Map<原链表节点，新链表节点>  原1=新1
        for(Node x=head;x!=null;x=x.next){
            Node node=new Node(x.val);
            nodeMap.put(x,node);
        }
        //对新链表进行操作 原1.next=新1.next 原1.random=新1.random  原1.next=原3>新1.next=新3(z这个地址可以根据原3取得)
        for (Node x=head;x!=null;x=x.next){
            nodeMap.get(x).next=nodeMap.get(x.next);
            nodeMap.get(x).random=nodeMap.get(x.random);
        }
        return nodeMap.get(head);
    }
}
